package algorithm;

import java.util.HashSet;
import java.util.Set;

public class ListNodeTest {
    public static void main(String[] args) {
        // ListNode head = ListNodeUtil.buildCircle();
        // 迭代法反转链表
        //ListNode newHead = reverse2(head);
        //System.out.println(newHead);
        // System.out.println(findLastK(head,6));
        // circleListNode(head);
        /*ListNode head1 = ListNodeUtil.build();
        ListNode head2 = ListNodeUtil.build2();
        ListNode commonListNode = commonListNode(head1, head2);
        if (commonListNode != null) {
            System.out.println(commonListNode.data);
        }*/
        //ListNode node = ListNodeUtil.build();
       /* ListNode lastK = deleteLastK(node, 5);
        if (lastK != null) {
            System.out.println(lastK);
        }*/
        ListNode listNode1 = ListNodeUtil.buildRepeat();
        circleListNode(listNode1);
    }

    private static void printListNode(ListNode head) {
        if (head == null) {
            return;
        }
        while (head != null) {
            System.out.print(head.data);
            head = head.next;
        }
    }

    // 递归反转
    private static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }


    // 迭代法反转
    private static ListNode reverse2(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            ListNode temp = cur.next;
            // 反转指针
            cur.next = prev;
            // 移动prev
            prev = cur;
            // 移动cur
            cur = temp;
        }
        return prev;
    }

    // 快指针先走k-1步，
    private static int findLastK(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < k - 1 && fast != null; i++) {
            fast = fast.next;
        }
        if (fast == null) {
            return -1;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        if (slow != null) {
            return slow.data;
        }
        return -1;
    }

    public static ListNode findCenter(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    public static boolean isListNodeCircle(ListNode head){
        if (head == null || head.next == null) {
            return false;
        }
        Set<ListNode> set = new HashSet<>();
        while (head.next != null) {
            if (set.contains(head)) {
                return true;
            }else {
                set.add(head);
                head = head.next;
            }
        }
        return false;
    }

    public static void circleListNode(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            // 快指针每次走两步，慢指针走一步，相遇的时候，说明链表有环
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                System.out.println("链表有环");
                break;
            }
        }
        // 寻找环的入口点，从相遇点和起点分别出发，下次相遇的点，就是环的入口
        ListNode meet = slow;
        ListNode begin = head;
        while (meet != null) {
            meet = meet.next;
            begin = begin.next;
            if (meet != null && meet == begin) {
                System.out.println("环的入口 " + meet.data);
                break;
            }
        }
        // 环的长度
        ListNode entry = slow;
        ListNode temp = slow;
        int length = 1;
        while (temp != null && temp.next != entry) {
            temp = temp.next;
            length++;
        }
        System.out.println("环的长度 " + length);
    }

    private static ListNode commonListNode(ListNode n1, ListNode n2) {
        int longLength = getListNodeLength(n1);
        int shortLength = getListNodeLength(n2);
        ListNode longNode = n1;
        ListNode shortNode = n2;
        int diff = longLength - shortLength;
        if (diff < 0) {
            longNode = n2;
            shortNode = n1;
            diff = -diff;
        }
        for (int i = 0; i < diff; i++) {
            longNode = longNode.next;
        }
        while (shortNode != null && longNode != null) {
            shortNode = shortNode.next;
            longNode = longNode.next;
            if (shortNode != null && longNode != null && shortNode.data == longNode.data) {
                return shortNode;
            }
        }
        return null;
    }


    private static int getListNodeLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode temp = head;
        int length = 1;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    // 删除链表的倒数第k个元素
    // 1-2-3-4-5
    private static ListNode deleteLastK(ListNode head, int k) {
        // 创建一个虚拟节点，用于处理删除头节点的情况
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        // 快指针先走k步，然后快慢指针一起走，等快指针到末尾的时候，慢指针就到了倒数第k-1个
        for (int i = 0; i < k && fast != null; i++) {
            fast = fast.next;
        }
        if (fast == null) {
            return head;
        }
        // 快慢指针一起走，等快指针到末尾的时候，慢指针就到了倒数第k-1个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 连接节点
        slow.next = slow.next.next;
        return dummy.next;
    }

    // 1-2-2-2-2-3-4-5
    private static ListNode deleteRepeatOne(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur!=null) {
            while (cur.next!=null&&cur.data == cur.next.data) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null) {
            if (slow.data != fast.data) {
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next;
        }
        // 最后一个不重复元素后面应该为null
       slow.next = null;
        return head;
    }

    // 1-2-3-4-5
    private static ListNode deleteCenter(ListNode head) {
        if (head == null || head.next == null || head.next.next==null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast =  head.next.next;
        while (fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    /**
     * 合并两个有序链表
     * @param l1 1 - 3- 5
     * @param l2 2 - 4- 6
     * @return 1 - 2 - 3 - 4 - 5 - 6
     */
    public static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        // 循环对比两个链表
        while (l1 != null && l2 != null) {
            if (l1.data < l2.data) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 将非空链表接在合并好的链表后
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return dummy.next;
    }
}
